package com.algorithm.learning.base.动态规划;

/**
 * @program: algorithm-learning
 * @description:
 * @author: YuKai Fan
 * @create: 2024/9/2 20:56
 **/
public class 汉诺塔问题 {

    public static void func(int n, String from, String to, String other) {
        // 当n==1时，表示只剩下最后一个盘子，一定是最大的盘子，可以直接从左移动到右
        if (n == 1) {
            System.out.println("Move 1 from " + from + " to " + to);
            return;
        }
        // 第一步：肯定要先把n-1上面的盘子，全部移到中间(这里的中间就是other)
        func(n - 1, from, other, to);
        // 这里就是打印过程
        System.out.println("move " + n + " from " + from + " to " + to);
        // 第三步：现在剩下的盘子都在中间，所以需要把中间的盘子全部移到右边（注意：这里的剩下的盘子在第一步中都在other上，所以是other -> to）
        func(n - 1, other, to, from);
    }

    public static void main(String[] args) {
        func(3, "left", "right", "middle");
    }
}
